package com.guan.poi.util;

import lombok.Getter;

/**
 * 位图合并工具类
 */
public class BitmapUtil {

    public static <T> void mergedRegion(T[][] arrays, IBitmapMerge mergeFunction) {
        if(arrays!=null && arrays.length!=0) {
            mergedRegion(arrays, 0, 0, arrays[0].length-1, mergeFunction);
        }
    }

    private static <T> void mergedRegion(T[][] arrays, int minRow, int minCel, int maxCel, IBitmapMerge mergeFunction) {
        int maxRow = arrays.length - 1;

        BitIndex startIndex = getNextIndex(arrays, minRow, minCel, maxCel);
        if(startIndex !=null) {
            if(startIndex.getCel() > minCel) {
                //非首列 左右分开处理
                mergedRegion(arrays, startIndex.getRow()+1, minCel, startIndex.getCel()-1, mergeFunction);
                mergedRegion(arrays, startIndex.getRow(), startIndex.getCel(), maxCel, mergeFunction);
            } else {
                BitIndex endIndex = getEndIndex(arrays, startIndex, minCel, maxCel);

                // 同行
                if(startIndex.getRow()==endIndex.getRow()) {
                    //最后一行
                    if(endIndex.getRow() == maxRow) {
                        mergeFunction.apply(startIndex, endIndex);
                        if(endIndex.getCel() < maxCel) {
                            mergedRegion(arrays, startIndex.getRow(), endIndex.getCel()+2, maxCel, mergeFunction);
                        }
                    } else if(endIndex.getCel() == maxCel){
                        //最后一列 上下分开处理
                        mergeFunction.apply(startIndex, endIndex);
                        mergedRegion(arrays, endIndex.getRow()+1, minCel, maxCel, mergeFunction);
                    } else {
                        //同一行 左右分开处理
                        mergedRegion(arrays, startIndex.getRow(), minCel, endIndex.getCel(), mergeFunction);
                        mergedRegion(arrays, startIndex.getRow(), endIndex.getCel()+1, maxCel, mergeFunction);
                    }
                } else {
                    //最后一列
                    if(endIndex.getCel() == maxCel){
                        //跨行 上下分开处理
                        mergeFunction.apply(startIndex, new BitIndex(endIndex.getRow(), maxCel));
                        if(endIndex.getRow() < maxRow) {
                            // 非最后一行
                            mergedRegion(arrays, endIndex.getRow()+1, minCel, maxCel, mergeFunction);
                        }
                    } else {
                        mergeFunction.apply(startIndex, new BitIndex(endIndex.getRow()-1, maxCel));
                        mergedRegion(arrays, endIndex.getRow(), minCel, maxCel, mergeFunction);
                    }


                }
            }
        }
    }

    private static <T> BitIndex getNextIndex(T[][] arrays, int minRow, int minCel, int maxCel) {
        for (int row = minRow; row < arrays.length; row++) {
            T[] array = arrays[row];
            for (int cel = minCel; cel <= maxCel; cel++) {
                if(array[cel] != null) {
                    return new BitIndex(row, cel);
                }
            }
        }
        return null;
    }


    private static <T> BitIndex getEndIndex(T[][] arrays, BitIndex excludeIndex, int minCel, int maxCel) {
        BitIndex emptyIndex = getEmptyIndex(arrays, excludeIndex, minCel, maxCel);
        if(emptyIndex==null) {
            return new BitIndex(arrays.length-1, maxCel);
        }
        int row = emptyIndex.getRow();
        return emptyIndex.getCel() == minCel ? new BitIndex(row - 1, maxCel) : new BitIndex(row, emptyIndex.getCel() - 1);
    }


    private static <T> BitIndex getEmptyIndex(T[][] arrays, BitIndex excludeIndex, int minCel, int maxCel) {
        int minRow = excludeIndex.getRow();
        T[] fisrtRow = arrays[minRow];
        for (int cel = excludeIndex.getCel()+1; cel <= maxCel; cel++) {
            if(fisrtRow[cel] == null) {
                return new BitIndex(minRow, cel);
            }
        }
        if (minRow + 1 < arrays.length) {
            for (int row = minRow +1; row < arrays.length; row++) {
                T[] array = arrays[row];
                for (int cel = minCel; cel <= maxCel; cel++) {
                    if(array[cel] == null) {
                        return new BitIndex(row, cel);
                    }
                }
            }
        }
        return null;
    }

    public interface IBitmapMerge {
        void apply(BitIndex t1, BitIndex t2);
    }

    @Getter
    public static class BitIndex {
        private final int row;
        private final int cel;

        BitIndex(int row, int cel) {
            this.row = row;
            this.cel = cel;
        }
    }

    public static void main(String[] args) {
        Integer[][] integers = new Integer[1][9];
        integers[0] = new Integer[]{0, null, 0, null, 0, null, 0, null, 0};

        mergedRegion(integers, (a, b)->{
            System.out.println(a.getCel()+":"+a.getRow() +"-"+b.getCel()+":"+b.getRow());
        });
    }
}
